package com.gaofeng.algo.java;

public class BinarySearchJava {

    public int mySqrt(int a) {
        if (a == 0) {
            return a;
        }
        int lo = 1;
        int hi = a;
        int mid;
        int sqrt;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            sqrt = a / mid;
            if (sqrt == mid) {
                return mid;
            } else if (sqrt > mid) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }

    public int[] searchRange(int[] numbs, int target) {
        if (numbs.length == 0) {
            return new int[]{-1, -1};
        }
        int lower = lowerBound(numbs, target);
        int upper = upperBound(numbs, target) - 1;
        if (lower == numbs.length || numbs[lower] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{lower, upper};
    }

    private int lowerBound(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length;
        int mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (numbers[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private int upperBound(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length;
        int mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (numbers[mid] > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    /**
     * 题目描述
     * 一个原本增序的数组被首尾相连后按某个位置断开（如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一
     * 位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组
     * 中。
     * 输入输出样例
     * 输入是一个数组和一个值，输出是一个布尔值，表示数组中是否存在该值。
     * Input: nums = [2,5,6,0,0,1,2], target = 0
     * Output: true
     *
     * @param nums
     * @param target
     * @return
     */
    public boolean search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        int mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return true;
            }
            //如果中间位置的元素==起始位置的元素,就无法判断哪边是升序的,所以将起始位置自增
            if (nums[lo] == nums[mid]) {
                lo++;
            } else if (nums[mid] <= nums[hi]) {
                //右边是有序的,
                //目标值>中间的元素,并且小于结束位置的元素,就把起始位置移到中间位置的下一个位置
                if (nums[hi] >= target && nums[mid] < target) {
                    lo = mid + 1;
                } else {
                    //否则结束位置左移
                    hi = mid - 1;
                }
            } else {
                //左边有序
                //目标值<中间位置的值,并且大于等于低位的值,则高位往中间移动
                if (nums[lo] <= target && nums[mid] > target) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }

        }
        return false;
    }
}
